/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/30 18:54
 */
// 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
    // 试一下递归解法
public class Solution92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        // 找起始节点
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode successor = null;
    // 反转后个节点
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }

        // 递归的获取子反转链表的起始节点
        ListNode last = reverseN(head.next, n - 1);
        // 反转
        head.next.next = head;
        head.next = successor;
        return last;
    }
}
